/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/meeting-rooms-ii
   @Language: C++
   @Datetime: 19-05-07 16:05
   */

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

class Solution {
	struct intervalhash{
		size_t operator()(const Interval &i)const{
			return i.start;
		}
		bool operator()(const Interval &a, const Interval &b)const{
			return a.start==b.start && a.end==b.end;
		}
	};
	static bool intervaless(const Interval &a, const Interval &b){
		return a.start<b.start;
	}
public:
	/**
	 * @param intervals: an array of meeting time intervals
	 * @return: the minimum number of conference rooms required
	 */
	int minMeetingRooms(vector<Interval> &intervals) {
		// Write your code here
		vector<unordered_set<Interval,intervalhash,intervalhash> > vs;
		sort(intervals.begin(),intervals.end(),intervaless);
		for(const auto &i:intervals){
			bool insert=false;
			for(auto &s:vs){
				if(insert) break;
				bool conflict = false;
				for(const auto &j:s){
					if(i.end<j.start || j.end<i.start) continue;
					conflict=true;
					break;
				}
				if(!conflict){
					s.insert(i);
					insert=true;
				}
			}
			if(!insert) vs.push_back({i});
		}
		return vs.size();
	}
};
